package com.data_structure_test.tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Stack;
import java.util.TreeMap;

/**
 * 树的深度优先遍历和广度优先遍历，
 * 
 * 对于深度优先遍历，  同一颗树的顺序一定是在一起的，不会出现   先到a树，在未遍历完a树的情况下，又遍历到b树。所以其的遍历只需要该颗树的信息。
 * 因此，深度优先遍历可以在不传整体信息的情况下使用递归进行。。
 * 深度优先遍历，也可以利用循环，将根据不同遍历种类，将路径存在栈中，再通过取栈来遍历。这种方式空间会有浪费，因为并没有必要去记录公有的顺序信息，分治时没有互相依赖的数据。
 * 
 * 广度优先遍历，在遍历到a树的情况下，是有可能在其未被遍历完时，就遍历其他树。所以其遍历在进行分治时，需要有一个公共的整体顺序信息传入，否则进行分治时就会增加复杂度。
 * 相比之下，利用循环设定queue就会比较方便
 * 
 * 
 * 
 * 此实现为中序遍历 ，按左小 中中  右大的顺序。 是链表实现
 * 
 * @author Dusk
 *
 * @param <T>
 */
public class BinaryTree<T> {
	
	private transient Node<T> rootNode;
	
	private int size = 0;

	public  class Node<T>{
		
		Node<T> parent;
		T value;
		Node<T> left;
		Node<T> right;
		public Node(BinaryTree.Node parent, T value, BinaryTree.Node left, BinaryTree.Node right) {
			super();
			this.parent = parent;
			this.value = value;
			this.left = left;
			this.right = right;
		}
		
		public void addLeftChild(T childValue){
			Node<T> child = new Node(this, childValue, null, null);
			this.left = child;
			size ++;
		}
		
		public void addRightChild(T childValue){
			Node<T> child = new Node(this,childValue, null,null);
			this.right = child;
			size ++;
		}
		
		private Node<T> findMin(Node<T> root){
			Node<T> tmp = root;
			while(tmp.left != null){
				tmp = tmp.left;
			}
			return tmp;
		}

		public void deleteItSelf() {
			if(this.parent == null){
				rootNode = null;
			}else{
				if(this.left == null && this.right == null){
					if(this.parent.left == this){
						this.parent.left = null;
						this.parent = null;
					}else{
						this.parent.right = null;
						this.parent = null;
					}
				}else if(this.left != null && this.right == null){
					if(this.parent.left == this){
						this.parent.left = this.left;
						this.parent = null;
					}else{
						this.parent.right = this.left;
						this.parent = null;
					}
				}else if(this.left == null && this.right != null){
					if(this.parent.left == this){
						this.parent.left = this.right;
						this.parent = null;
					}else{
						this.parent.right = this.right;
						this.parent = null;
					}
				}else{
					Node<T> rightMin = this.findMin(this.right);
					this.value = rightMin.value;
					rightMin.deleteItSelf();
				}
			}
		}
	}
	
	public BinaryTree(){
	}
	
	
	
	//构造
	public void add(T value){
		Node<T> tmp,last = null;
		if((tmp = rootNode) == null){
			rootNode = new Node(null, value, null, null);
			size ++;
		}else{
			while(tmp != null){
				last = tmp;
				if(value.hashCode() > tmp.value.hashCode() ){
					tmp = tmp.right;
				}else{
					tmp = tmp.left;
				}
			}
			if(value.hashCode() > last.value.hashCode() ){
				last.addRightChild(value);
			}else{
				last.addLeftChild(value);
			}
			
		}
	}
	
	public int delete(T value){
		Node<T> node = findNodeByValue(value);
		if(node != null){
			node.deleteItSelf();
			return 1;
		}
		return 0;
	}

	private Node<T> findNodeByValue(T value) {
		Node<T> tmp,res = null;
		if((tmp = rootNode) != null){
			while(tmp != null){
				if(value.hashCode() > tmp.value.hashCode()){
					tmp = tmp.right;
				}else if(value.hashCode() < tmp.value.hashCode()){
					tmp = tmp.left;
				}else{
					res = tmp;
					break;
				}
			}
		}
		return res;
	}
	
	public boolean contains(T value){
		return findNodeByValue(value) != null;
	}
	
	public List<T> getIntoList(){
		
		List<T> list = new ArrayList<>();
		
		forEachAndInject(rootNode,list);
		
		return list;
	}
	
	
	//递归
	private void forEachAndInject(BinaryTree<T>.Node<T> parent, List<T> list) {
		
		if(parent.left != null){
			forEachAndInject(parent.left,list);
		}
		
		list.add(parent.value);
		
		if(parent.right != null){
			forEachAndInject(parent.right,list);
		}
	}
	
	
	public List<T> getWhileList(){
		
		List<T> list = new ArrayList<>();
		
		forEachAndInjectWhile(rootNode,list);
		
		return list;
	}



	private void forEachAndInjectWhile(BinaryTree<T>.Node<T> root, List<T> list) {
		Stack<BinaryTree<T>.Node<T>> stack = new Stack<>();
		BinaryTree<T>.Node<T> searchPoint = root;
		while(searchPoint != null||!stack.isEmpty()){
			BinaryTree<T>.Node<T> tmp;
			while(searchPoint != null){
				stack.push(searchPoint);
				searchPoint = searchPoint.left;	
			}
			tmp = stack.pop();
			list.add(tmp.value);
			searchPoint = tmp.right;
		}
		
	}
	
	public List<T> getWhileListSpaceSave(){
		List<T> list = new ArrayList<>();
		
		forEachAndInjectWhileSpaceSave(rootNode,list);
		
		return list;
	}



	private void forEachAndInjectWhileSpaceSave(BinaryTree<T>.Node<T> rootNode, List<T> list) {
		BinaryTree<T>.Node<T> top = null,searchPoint = rootNode;
		int size = 0;
		while(size < this.size){
			while(searchPoint != null){
				top = searchPoint;
				searchPoint = searchPoint.left;
			}
			list.add(top.value);
			size ++;
			searchPoint = top.right;
			if(top.right == null){
				top = next(top);
			}
		}
		
	}



	private BinaryTree<T>.Node<T> next(BinaryTree<T>.Node<T> top) {
		
		if(top.parent == null){
			return null;
		}
		
		while(top.parent.right == top){
			top = top.parent;
			if(top.parent == null){
				return null;
			}
		}
		top = top.parent;
		return top;
	}



	public static void main(String[] args) {
		Random rand = new Random();
		int num = 10;
		int range = 1000000;
		int check = 1;
		BinaryTree<Integer> binaryTree = new BinaryTree<Integer>();
		BinaryAvlTree<Integer> avlTree = new BinaryAvlTree<>();
		ArrayList<Integer> list = new ArrayList<>();

		long insertBefore = System.currentTimeMillis();
		for(int i = 0;i < num;i++){
			int toAdd = rand.nextInt(range);
			//binaryTree.add(toAdd);
			avlTree.insert(toAdd);
			//list.add(toAdd);
		}
		long insertAfter = System.currentTimeMillis();
		System.out.println(insertAfter - insertBefore);

		System.out.println(System.currentTimeMillis());
		//System.out.println(binaryTree.contains(check));
		//System.out.println(list.contains(check));
        System.out.println(avlTree.containsRecursion(check));
		System.out.println(System.currentTimeMillis());
		
		System.out.println(avlTree.foreachZhongRecursive());
		System.out.println(avlTree.foreachZhongWhile());//parent设错,应该是左旋时导致。
		
		
		
		
	/*	long whilesaveBeforeTime = System.currentTimeMillis();
		//System.out.println(binaryTree.getWhileList());
		binaryTree.getWhileListSpaceSave();
		long whilesaveAfterTime = System.currentTimeMillis();
		System.out.println(whilesaveAfterTime - whilesaveBeforeTime);
		
		long intoBeforeTime = System.currentTimeMillis();
		//System.out.println(binaryTree.getWhileListSpaceSave());
		binaryTree.getIntoList();
		long intoAfterTime = System.currentTimeMillis();
		System.out.println(intoAfterTime - intoBeforeTime);
		
		long whileBeforeTime = System.currentTimeMillis();
		//System.out.println(binaryTree.getWhileList());
		binaryTree.getWhileList();
		long whileAfterTime = System.currentTimeMillis();
		System.out.println(whileAfterTime - whileBeforeTime);
		*/
		/*System.out.println(System.currentTimeMillis());
		//System.out.println(binaryTree.contains(5));
		System.out.println(list.contains(check));
		System.out.println(System.currentTimeMillis());*/
		
		
		
	}

}
